#include <stdio.h>

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void AdjustUp(int* arr, int child)
{
	int parent = (child - 1) / 2; //父节点的下标
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void AdjustDown(int* arr, int n, int parent)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		//先选出较小的节点
		if (child + 1 < n
			&& arr[child + 1] > arr[child])
			child = child + 1;
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else 
			break;
	}
}

void HeapSort(int arr[], int len)
{
	//建堆，才用自下而上的方法时间复杂度为O( N )
	//		若才用自顶向下的方法，时间复杂度为O( N * logN)

	//升序建大根堆
	//降序建小根堆
	int father = ((len - 1) - 1) / 2;
	while (father > 0)
	{
		AdjustDown(arr, len, father);
		father--;
	}

	int end = len - 1;
	
	
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}

	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	int len = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, len);
	return 0;
}